UVa/11846 - Finding Seats Again/11846.cpp

   1 // This times out!
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 const int MAXN = 20;
  29 const int MAXK = 27;
  30
  31 struct region {
  32     short r1, r2, c1, c2;
  33     region() {}
  34     region(short r1, short r2, short c1, short c2) : r1(r1), r2(r2), c1(c1), c2(c2) {}
  35 };
  36
  37 struct cell {
  38     short r, c;
  39     cell() {}
  40     cell(short r, short c) : r(r), c(c) {}
  41 };
  42
  43 int N, K;
  44 char mat[MAXN][MAXN];
  45 cell leaders[MAXK];
  46 int people[MAXK];
  47 vector< region > options[MAXK];
  48
  49 inline bool valid(const region& r) {
  50     return (0 <= r.r1 and r.r1 <= r.r2 and r.r2 < N and
  51         0 <= r.c1 and r.c1 <= r.c2 and r.c2 < N);
  52 }
  53
  54 inline bool containsCell(const region &rg, int r, int c) {
  55     return rg.r1 <= r and r <= rg.r2 and rg.c1 <= c and c <= rg.c2;
  56 }
  57
  58 inline bool containsDifferentLetter(const region &r, char letter) {
  59     //assert(valid(r));
  60     for (int i = r.r1; i <= r.r2; ++i) {
  61         for (int j = r.c1; j <= r.c2; ++j) {
  62             if (mat[i][j] != '.' and mat[i][j] != letter) return true;
  63         }
  64     }
  65     return false;
  66 }
  67
  68 inline bool sameLetterOutsideRegion(const region &r, char letter) {
  69     for (int i = 0; i < N; ++i) {
  70         for (int j = 0; j < N; ++j) {
  71             if (containsCell(r, i, j)) continue;
  72             if (mat[i][j] != '.' and mat[i][j] == letter) return true;
  73         }
  74     }
  75     return false;
  76
  77 }
  78
  79 inline bool containsEmptyCell(const region &r) {
  80     //assert(valid(r));
  81     for (int i = r.r1; i <= r.r2; ++i) {
  82         for (int j = r.c1; j <= r.c2; ++j) {
  83             if (mat[i][j] == '.') return true;
  84         }
  85     }
  86     return false;
  87 }
  88
  89
  90 inline void fillRegion(const region &r, char letter) {
  91     //assert(valid(r));
  92     for (int i = r.r1; i <= r.r2; ++i) {
  93         for (int j = r.c1; j <= r.c2; ++j) {
  94             mat[i][j] = letter;
  95         }
  96     }
  97 }
  98
  99 bool deduceFixedPositions() {
 100     bool changed = false;
 101
 102     for (int k = 0; k < K; ++k) {
 103         int oldOptionsSize = options[k].size();
 104
 105         options[k].clear();
 106
 107         int size = people[k];
 108         for (int width = 1; width <= size; ++width) {
 109             if (size % width != 0) continue;
 110             int height = size / width;
 111             char leaderLetter = mat[leaders[k].r][leaders[k].c];
 112
 113             for (int i = max(0, leaders[k].r - height + 1); i + height - 1 < N and i <= leaders[k].r; ++i) {
 114                 for (int j = max(0, leaders[k].c - width + 1); j + width - 1 < N and j <= leaders[k].c; ++j) {
 115                     region r(i, i + height - 1, j, j + width - 1);
 116                     assert(valid(r));
 117                     assert(containsCell(r, leaders[k].r, leaders[k].c));
 118                     //printf("considering region <r1=%d, r2=%d, c1=%d, c2=%d> for leader %d\n", r.r1, r.r2, r.c1, r.c2, k);
 119                     if (containsDifferentLetter(r, leaderLetter)) {
 120                         //printf("discarding because it also has a different letter\n");
 121                         continue;
 122                     }
 123                     if (sameLetterOutsideRegion(r, leaderLetter)) {
 124                         //printf("discarding because this letter is also outside this region\n");
 125                         continue;
 126                     }
 127                     options[k].push_back( r );
 128                 }
 129             }
 130         }
 131
 132         if (oldOptionsSize != options[k].size()) {
 133             changed = true;
 134         }
 135
 136         if (options[k].size() == 1 and containsEmptyCell(options[k][0])) {
 137             fillRegion(options[k][0], 'A' + k);
 138             changed = true;
 139         }
 140
 141         //for (int i = 0; i < options[k].size(); ++i){ region r = options[k][i]; printf("There's a possible region for leader %d at <r1=%d, r2=%d, c1=%d, c2=%d>\n", k, r.r1, r.r2, r.c1, r.c2); }
 142     }
 143
 144     //for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { printf("%c", mat[i][j]); } puts(""); }
 145
 146     if (changed) return true;
 147
 148     // Place a letter where there's only a possible leader that covers that cell
 149     for (int i = 0; i < N; ++i) {
 150         for (int j = 0; j < N; ++j) {
 151             if (mat[i][j] != '.') continue;
 152             int leaderThatContainsMe = -1; int numberOfLeadersThatContainMe = 0;
 153             for (int k = 0; k < K; ++k) {
 154                 for (int o = 0; o < options[k].size(); ++o) {
 155                     if (containsCell(options[k][o], i, j)) {
 156                         leaderThatContainsMe = k;
 157                         numberOfLeadersThatContainMe++;
 158                         break;
 159                     }
 160                 }
 161             }
 162             //printf("cell <%d, %d>: number of leaders that contain me = %d\n", i, j, numberOfLeadersThatContainMe);
 163             //assert(numberOfLeadersThatContainMe > 0);
 164             if (numberOfLeadersThatContainMe == 1) {
 165                 mat[i][j] = leaderThatContainsMe + 'A';
 166                 changed = true;
 167             }
 168         }
 169     }
 170
 171     //for (int k = 0; k < K; ++k) for (int i = 0; i < options[k].size(); ++i){ region r = options[k][i]; printf("There's a possible region for leader %d at <r1=%d, r2=%d, c1=%d, c2=%d>\n", k, r.r1, r.r2, r.c1, r.c2); }
 172
 173     if (changed) return true;
 174
 175     return false;
 176 }
 177
 178 bool cellWith0CoveringRegions() {
 179     for (int i = 0; i < N; ++i) {
 180         for (int j = 0; j < N; ++j) {
 181             for (int k = 0; k < K; ++k) {
 182                 char letter = 'A' + k;
 183                 for (int o = 0; o < options[k].size(); ++o) {
 184                     const region &r = options[k][o];
 185                     if (!containsCell(r, i, j)) continue;
 186                     if (sameLetterOutsideRegion(r, letter)) continue; // can't take this one
 187                     if (containsDifferentLetter(r, letter)) continue;
 188                     return false;
 189                 }
 190             }
 191         }
 192     }
 193     return true;
 194 }
 195
 196 bool backtrack(int k, int placed) {
 197     //printf("k = %d, K = %d\n", k, K);
 198     //for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { printf("%c", mat[i][j]); } puts(""); }
 199
 200     if (k == K or placed == k) {
 201         // Found solution!
 202         for (int i = 0; i < N; ++i) {
 203           for (int j = 0; j < N; ++j) {
 204             putchar(mat[i][j]);
 205           }
 206           putchar('\n');
 207         }
 208         return true;
 209     }
 210
 211
 212     if (cellWith0CoveringRegions()) return false;
 213
 214     //for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { printf("%c", mat[i][j]); } puts(""); }
 215
 216     char letter = mat[leaders[k].r][leaders[k].c];
 217
 218     for (int o = 0; o < options[k].size(); ++o) {
 219         const region &r = options[k][o];
 220         // let's take this region
 221         if (sameLetterOutsideRegion(r, letter)) continue; // can't take this one
 222         if (containsDifferentLetter(r, letter)) continue;
 223
 224         vector< cell > changed;
 225         for (int i = r.r1; i <= r.r2; ++i) {
 226             for (int j = r.c1; j <= r.c2; ++j) {
 227                 assert(mat[i][j] == '.' or mat[i][j] == letter);
 228                 if (mat[i][j] == '.') {
 229                     changed.push_back ( cell(i, j)  );
 230                     mat[i][j] = letter;
 231                 }
 232             }
 233         }
 234         if (backtrack(k + 1, placed + 1)) return true;
 235
 236         for (int c = 0; c < changed.size(); ++c) {
 237             mat[changed[c].r][changed[c].c] = '.';
 238         }
 239     }
 240     return false;
 241 }
 242
 243 int main(){
 244     while (scanf("%d %d", &N, &K) == 2) {
 245         int currentLeader = 0;
 246         for (int i = 0; i < N; ++i) {
 247             for (int j = 0; j < N; ++j) {
 248                 char c = getchar(); while (isspace(c)) c = getchar();
 249                 mat[i][j] = c;
 250                 if (isdigit(c)) {
 251                     leaders[currentLeader] = cell(i, j);
 252                     people[currentLeader] = c - '0';
 253                     options[currentLeader].clear();
 254                     mat[i][j] = 'A' + currentLeader;
 255                     currentLeader++;
 256                 }
 257             }
 258         }
 259
 260         // sort leaders by size
 261         for (int i = 0; i < K; ++i) {
 262             for (int j = i + 1; j < K; ++j) {
 263                 if (people[j] > people[i]) {
 264                     swap(mat[leaders[i].r][leaders[i].c], mat[leaders[j].r][leaders[j].c]);
 265                     swap(leaders[i], leaders[j]);
 266                     swap(people[i], people[j]);
 267                 }
 268             }
 269         }
 270
 271         //for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { printf("%c", mat[i][j]); } puts(""); }
 272         //
 273         // for (int i = 0; i < K; ++i) {
 274         //     printf("There's a leader at <%d, %d> of size %d\n", leaders[i].r, leaders[i].c, people[i]);
 275         // }
 276
 277         bool changed = true;
 278         while (changed) {
 279             changed = deduceFixedPositions();
 280         }
 281
 282         // for (int i = 0; i < N; ++i) {
 283         //   for (int j = 0; j < N; ++j) {
 284         //     printf("%c", mat[i][j]);
 285         //   }
 286         //   printf("\n");
 287         // }
 288         int count = 0;
 289         for (int k = 0; k < K; ++k) {
 290             int seen = 0;
 291             for (int i = 0; i < N; ++i) {
 292                 for (int j = 0; j < N; ++j) {
 293                     seen += (mat[i][j] == 'A' + k);
 294                 }
 295             }
 296             count += (seen == people[k]);
 297         }
 298         assert(backtrack(0, count));
 299     }
 300     return 0;
 301 }